package org.java.mianshiya.javaBasic;

/**
 * @Auther: qingle
 * @Date: 2024/11/25-19:53
 * @Description:
 * @version: 1.0
 */
public class Trie {
	private TrieNode root;

	public Trie() {
		root = new TrieNode();
	}

	// insert
	public void insert(String word) {
		TrieNode current = root;
		for (char ch: word.toCharArray()
		) {
			current = current.childern.computeIfAbsent(ch, c->
				new TrieNode());
		}
		current.isEndOfWord = true;
	}

	// insert
	public boolean search(String word) {
		TrieNode current = root;
		for (char ch: word.toCharArray()
		) {
			TrieNode node = current.childern.get(ch);
			if(node == null) {
				return false;
			}
			current = node;
		}
		return current.isEndOfWord;
	}

	// startWith perfix
	public boolean startWith(String perfix) {
		TrieNode current = root;
		for (char ch: perfix.toCharArray()
		) {
			TrieNode node = current.childern.get(ch);
			if(node == null) {
				return false;
			}
			current = node;
		}
		return true;
	}

	public static void main(String[] args) {
		Trie trie = new Trie();

		// 插入一些words
		trie.insert("abc");
		trie.insert("app");
		trie.insert("");
		trie.insert("apple");

		// search
		System.out.println("search:---------");
		System.out.println(trie.search("apple"));
		System.out.println(trie.search("app"));
		System.out.println(trie.search("app"));
		System.out.println(trie.search("abc"));
		System.out.println(trie.search("ab"));
		System.out.println(trie.search("abcd"));

		// check
		System.out.println("check:---------");
		System.out.println(trie.startWith("app"));
		System.out.println(trie.startWith("apple"));
		System.out.println(trie.startWith("ab"));
		System.out.println(trie.startWith("appled"));
		System.out.println(trie.startWith("cat"));
	}

}